1583. Count Unhappy Friends

题目 1583. Count Unhappy Friends

思路分析

因为最后一定会两两配对

猜想：只要不是某个人的首选 就一定不满意

貌似成立

class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // 1. 构建每个人的“首选” 
        // firstChoice[i] 表示 i 最想跟谁在一起
        int[] firstChoice = new int[n];
        for (int i = 0; i < n; i++) {
            firstChoice[i] = preferences[i][0]; // 索引 0 才是最喜欢的
        }

        // 2. 构建实际分配 (pair_true)
        // mate[i] = j 表示 i 当前的对象是 j
        int[] mate = new int[n];
        for (int[] p : pairs) {
            mate[p[0]] = p[1];
            mate[p[1]] = p[0];
        }

        // 3. 比较：如果实际对象 != 首选对象，就算不开心
        int unhappyCount = 0;
        for (int i = 0; i < n; i++) {
            int myActualPartner = mate[i];
            int myDreamPartner = firstChoice[i];

            if (myActualPartner != myDreamPartner) {
                unhappyCount++;
            }
        }
        
        return unhappyCount;
    }
}

但实际上不成立。

虽然直觉上没得到最好的肯定不爽，但这道题定义的“不开心”是双向奔赴的。

假设 A 的首选是 B，但 A 被分给了 C。

• 按你的逻辑：A 不开心（因为没得到 B）。
• 按题目逻辑：
  • A 确实想找 B。
  • 但是，如果 B 的当前对象是 D，而且 B 喜欢 D 胜过喜欢 A。
  • 这时候，A 虽然想找 B，但 B 不想理 A。
  • 在这种情况下，A 只能认命，不算题目定义的“不开心朋友”。

题目中“不开心”的条件是：A 想找 B，而且 B 也觉得 A 比自己现在的对象好（双方都有出轨意愿），这才叫 Unhappy。

需要判断的不是“是否匹配了首选”，而是“是否存在一个比当前对象更好，且对方也觉得你更好的人”。

代码实现

class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // map: 记录每个人的实际配对对象
        // 作用：mate[i] = j 表示 i 和 j 是一对
        int[] mate = new int[n];
        for (int[] p : pairs) {
            mate[p[0]] = p[1];
            mate[p[1]] = p[0];
        }

        // map: 预处理亲密度排名表
        // 作用：rank[i][j] = k 表示：在 i 的心里，j 排在第 k 位（越小越好）
        // 这样我们比较亲密度时，就不需要遍历数组，直接对比整数大小即可
        int[][] rank = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n - 1; k++) {
                int person = preferences[i][k];
                rank[i][person] = k;
            }
        }

        int unhappyCount = 0;

        // 遍历每一个人 x，检查他是否不开心
        for (int x = 0; x < n; x++) {
            int y = mate[x]; // y 是 x 当前的实际对象
            int indexY = rank[x][y]; // y 在 x 心里的排名

            // 核心逻辑：
            // 我们遍历 x 的偏好列表，只看那些 排在 y 前面 的人（即 x 更喜欢的人）
            // 假设 x 更喜欢 u (u 排在 y 前面)
            for (int k = 0; k < indexY; k++) {
                int u = preferences[x][k]; 
                int v = mate[u]; // v 是 u 当前的实际对象
                
                // 此时已知：x 喜欢 u > y
                // 必须检查：u 是否也喜欢 x > v ？
                // 如果是双向奔赴（两边都觉得对方比现任好），那么 x 就是不开心的
                if (rank[u][x] < rank[u][v]) {
                    unhappyCount++;
                    break; // x 已经确定不开心了，不需要再找其他出轨对象了，统计下一个 x
                }
            }
        }

        return unhappyCount;
    }
}

假设我们正在判断 x 是否不开心：

1. x 的现状：跟 y 在一起。
2. x 的心声：查看 x 的 preferences 列表。
   • 如果列表里有一个人 u，排在 y 前面。
   • 说明：x 喜欢 u > x 喜欢 y。
3. u 的现状：跟 v 在一起。
4. u 的心声：利用 rank 矩阵快速查看。
   • 如果 rank[u][x] < rank[u][v]。
   • 说明：u 喜欢 x > u 喜欢 v。
5. 结论：两人都觉得对方比现任好，x 是不开心的（同理 u 也是不开心的，会在 u 的循环里被统计到）。

做不来这么渣的题，，，

同类题型

视频讲解